#ifdef LOCAL
#include <bits/stdc++.h>
using namespace std;
#endif

class Solution {
public:
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    };

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int n = preorder.size();
        for (int num: preorder) {
            for (int i = 0; i < n; i++)
                if (inorder[i] == num) hash[num] = i;
        }
        TreeNode *tree = myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
        return tree;
    }

    unordered_map<int, int> hash;

    TreeNode *myBuildTree(vector<int> &preorder, vector<int> &inorder, int preL, int preR, int inL, int inR) {
        if (inR < inL) return nullptr;
        TreeNode *root = new TreeNode(preorder[preL]);
        int in_index = hash[preorder[preL]];
        int left_num = in_index - inL;
        int right_num = inR - in_index;
        root->left = myBuildTree(preorder, inorder, preL + 1, preL + left_num, inL, in_index - 1);
        root->right = myBuildTree(preorder, inorder, preL + left_num + 1, preL + left_num + right_num, in_index + 1,
                                  inR);
        return root;
    }
};

#ifdef LOCAL

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

int main() {
    Solution solution;
    vector<int> preorder{3,9,20,15,7};
    vector<int> inorder{9,3,15,20,7};
    solution.buildTree(preorder,inorder);
}

#endif